package com.xigua._双指针;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @author LiRongHua
 * @Title: ${file_name}
 * @Package ${package_name}
 * @Description: ${todo}
 * @date 2022/4/216:38
 */
public class _28_四数之和 {

    public static void main(String[] args) {
        fourSum(new int[]{1,-2,-5,-4,-3,3,3,5},-11);
    }

    public static List<List<Integer>> fourSum(int[] nums, int target) {
        List<List<Integer>> ans = new ArrayList<>(200);
        int n = nums.length;
        Arrays.sort(nums);
        for (int i = 0; i < n-3; i++) {
            if (i != 0 && nums[i] == nums[i-1]) continue;
            if (nums[i] > target && target >0) return ans;
            for (int j = i+1; j < n-2; j++) {
                if (j != i+1 && nums[j] == nums[j-1]) continue;
                if (nums[i]+nums[j] >target && target >0) break;
                int x = j+1;
                int y = n-1;
                while (x<y) {
                    int sum = nums[i] + nums[j] + nums[x] + nums[y];
                    if (sum > target) {
                        while (y>x && nums[y]==nums[--y]);
                    } else if (sum < target) {
                        while (y>x && nums[x] == nums[++x]);
                    } else {
                        ans.add(Arrays.asList(nums[i],nums[j],nums[x],nums[y]));
                        while (y>x && nums[y]==nums[--y]);
                        while (y>x && nums[x] == nums[++x]);
                    }
                }
            }
        }
        return ans;

    }

}
